public class Solution2 {
    public static void main(String[] args) {
        //1,1,2,3,5,....
        int[][] x={{1,1},{1,0}};
        int n = 11;
        Solution2 solution2 = new Solution2();
        int[][] mi = solution2.mi(x, n - 2);
        int i = mi[0][0]+mi[0][1];
        System.out.println(i);
     }

    // 计算x的n次幂
    public int[][] mi(int[][] x,int n){
        int[][] i={{1,0},{0,1}};
        int[][] v=x;
        if(n==1){
            return x;
        }
        while(n != 0){
            if(n%2 ==1){
                i = multi(i,v);
                n-=1;
            }
            v= multi(v,v);
            n = n/2;
        }
        return i;
    }

    private int[][] multi(int[][] v1, int[][] v2) {
        int[] num1 = {v1[0][0]*v2[0][0]+v1[0][1]*v2[1][0],v1[0][0]*v2[0][1]+v1[0][1]*v2[1][1]};
        int[] num2 = {v1[1][0]*v2[0][0]+v1[1][1]*v2[1][0],v1[1][0]*v2[0][1]+v1[1][1]*v2[1][1]};
        return new int[][]{num1,num2};
    }
}
